//
// Created by hcDarren on 2018/8/26.
// .hpp支持泛型。

#ifndef NDK_DAY39_AS_ARRAYQUEUE_H
#define NDK_DAY39_AS_ARRAYQUEUE_H

#include <malloc.h>

template<class E>
class ArrayQueue {
private:
    // 2 的幂次，数组的大小。
    int size = 0;
    // 队列头索引
    int head = 0;
    // 队列的尾巴索引
    int tail = 0;
    // 数组地址，存放数据
    E *array;

public:
    ArrayQueue();

    ArrayQueue(int size);

    ~ArrayQueue();

public:
    bool isEmpty(); // 是否为空

    // 移除队首的元素
    E pop();
    // 添加到队尾巴
    void push(E e);

    // 获取队首的位置，但是不移除item。
    E peek();

public:
    void growArray();

    void copyElement(E *array, int tail, E *new_array, int i, int r);
};

template<class E>
ArrayQueue<E>::ArrayQueue() : ArrayQueue(4) {
    // 默认原始大小。4
}

// 构造函数。
template<class E>
ArrayQueue<E>::ArrayQueue(int size) {// 3 -> 4, 6 ->8, 17 ->32
    // size是可以乱传的  但是要保证是 2 的幂次
    // 类似的代码：HashMap.java--tableSizeFor(int cap)
    int init_size = size;
    if (init_size >= 4) {
        init_size |= init_size >> 1; // 或等自己，右移1位。
        init_size |= init_size >> 2;
        init_size |= init_size >> 4;
        init_size |= init_size >> 8;
        init_size |= init_size >> 16; // 或等自己，右移16位。
        // 确保是2的幂次

        // int 4 字节  32
        init_size += 1; // 进一位，16可变成32.
    }
    this->size = init_size;
    array = (E *) malloc(sizeof(E) * size); // 开辟内存空间
}

template<class E>
void ArrayQueue<E>::push(E e) {
    // 与运算，做求模的功能。
    head = (head - 1) & (size - 1);// -1  size -1
    // &  2幂n   111111111  size 一定要是 2 的幂次
    array[head] = e;
    if (tail == head) { // 尾巴== head了，要扩容。避免越界。
        // 扩容 , 双端数列 头部增加删除功能，也可以在尾部增加删除，加两个方法测试
        growArray();
    }
}

template<class E>
E ArrayQueue<E>::peek() { // 拿到栈顶元素，但是不退出来。
    return array[(tail - 1) & (size - 1)];
}

template<class E>
E ArrayQueue<E>::pop() {
    tail = (tail - 1) & (size - 1);
    return array[tail];
}

template<class E>
bool ArrayQueue<E>::isEmpty() { // 是否为空
    return tail == head;
}

template<class E>
ArrayQueue<E>::~ArrayQueue() { // 析构函数
    free(array);
}

// 扩容：左移动一倍。
template<class E>
void ArrayQueue<E>::growArray() {
    // size += size >> 1;
    int new_size = size << 1;
    // 扩容，开辟一片数组。
    E *new_array = (E *) malloc(sizeof(E) * new_size);

    // 对数据进行 copy ,将 tail 后面的拷贝到前面，将tail前面的拷贝到后面。
    // 不能简单的realloc处理，要重新恢复位置。
    int r = size - tail;
    copyElement(array, tail, new_array, 0, r); // 原来的拷贝到新数组: 从tail位置考试拷贝，拷贝到0位置，拷贝r个。
    copyElement(array, 0, new_array, r, tail); // 从0位置开始，r开始放，拷贝tail个元素。

    free(array); // 释放array的内存。
    head = 0;
    tail = size;
    size = new_size; // 新数组的大小
    array = new_array; // 新数组赋值给array。
}

// 拷贝元素 sPo 开始的位置；
template<class E>
void ArrayQueue<E>::copyElement(E *src, int sPo, E *dest, int dPo, int len) {
    for (int i = 0; i < len; ++i) {
        dest[dPo + i] = src[sPo + i];
    }
}

#endif //NDK_DAY39_AS_ARRAYQUEUE_H
